Modular arithmetic coprocessors are typically used in encryption and/or decryption circuits. The use of these coprocessors enables a considerable acceleration of encryption and/or decryption operations using the Montgomery method. Such systems are commonly used in chip cards employing, in particular, the RSA code.
The RSA code is a form of mathematical encoding where a binary message M encoded on N bits is processed as an integer of n bits. The encryption and decryption are done by operations of modular exponentiation:
encryption: M'=M.sup.e mod N, PA1 decryption: M=M'.sup.d mod N.
Where M' is the encrypted message encoded on n bits, N is an integer encoded on n bits such that N=p*q, and p and q are two integers. The exponents e and d are two integers such that (e*d) mod .PHI.(N)=1, with .PHI.(N)=(p-1)*(q-1). A code of this kind therefore has two keys, one encryption key called a public key (e and N) and the other a decryption key called a secret key (d and N).
To find the secret key from the public key, it is enough to carry out the following operation: d=(1+K*.PHI.(N))/e, with K being an integer coefficient that is not zero. The security of a code of this kind lies in the complexity of the operations to be performed. To find the secret key, it is necessary to split up N into prime numbers. This requires a period of time that becomes greater as the numbers p and q are increased (p and q are encoded on several hundreds of bits). Indeed, it is necessary to test, successively, the divisibility of N by all the integers encoded on 2 to n/2 bits.
It is quite possible to find out the secret key from the public key, provided that several hundreds of years are spent for this purpose. However, certain uses of RSA codes may require changes of keys that make use of a computation of keys. Such computations may make use of divisions on large numbers.
In chip cards, the encryption circuits make use of a microprocessor-coprocessor type architecture. The microprocessor is a standard 8-bit or 16-bit microprocessor. The coprocessor is a modular arithmetic coprocessor especially designed to carry out computations on large numbers. The document EP-A 601,907 discloses a modular arithmetic coprocessor using a serial architecture that is particularly well suited to chip cards. This particularly well suited coprocessor has been used as a basis for several improvements, and especially for the patent application PCT/FR 97/00035.
The patent application PCT/FR 97/00035 discloses a possible performance of an integer division using the modular arithmetic coprocessor. However, the division made requires a reversal of bits on large-sized words for the dividend and the quotient. The reversal is done at present by a processor which works jointly with the coprocessor and requires, firstly, substantial memory space and, secondly, substantial computation time.